package leetcode_二分查找;

import java.util.Arrays;

/**
 * 两球之间的磁力
 * 算法: 二分查找
 * <p>
 * 最小磁力越小, 可以放的小球越多; 越大, 可以放的越少
 * 所以, [l, r] 相当于一个元素值递减的数组
 * </p>
 * 循环不变量: f(r + 1, position) 指向 < m 的位置, f(l - 1, position) 指向 >= m 的位置
 *
 * @author yezh
 * @date 2025/2/15 17:04
 */
public class _1552 {

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int l = 1, r = (position[position.length - 1] - position[0]) / (m - 1);
        while (l <= r) {
            int mid = l + (r - l) / 2;
            // 当最小磁力为 mid 时, 可以放的小球数量
            if (f(mid, position) < m) r = mid - 1;
            else l = mid + 1;
        }
        System.out.println(l + " " + r);
        return r;
    }

    int f(int d, int[] position) {
        int cnt = 1, pre = position[0];
        for (int p : position)
            if (p >= pre + d) {
                ++cnt;
                pre = p;
            }
        return cnt;
    }

}
